/*!
 * \file pqueue.c
 * \brief Implementation for the pqueue class.
 * \author Vijay Ramesh
 *
 * This is a simple queue class.
 */

#include "pqueue.h"

void pq_init ( pqueue_t *pqueue, funcp compare )
{
   pqueue->front = NULL;
   pqueue->back = NULL;
   pqueue->empty = TRUE;
   pqueue->size = 0;
   pqueue->less = compare;
   return;
}

int pq_enqueue ( pqueue_t *pqueue, void *value )
{
   pqnode_t *temp_node;
   temp_node = ( pqnode_t *) malloc ( sizeof ( pqnode_t ));
   if ( temp_node == NULL )
   {
      /* Out of memory */
      return 1;
   }
   else
   {
      temp_node->value = value;
      if ( pqueue->empty )
      {
         /* queue is empty */
         temp_node->next = NULL;
         temp_node->prev = NULL;
         pqueue->back = temp_node;
         pqueue->front = temp_node;
         /* Sucess */
      }
      else
      {
         /* queue is not empty */
         if ( pqueue->less ( temp_node->value, pqueue->front->value ) > 0 )
         {
            /* inserting at front of queue */
            pqueue->front->prev = temp_node;
            temp_node->next = pqueue->front;
            temp_node->prev = NULL;
            pqueue->front = temp_node;
         }
         else
         {
            pqnode_t *temp = pqueue->back;
            int diff = pqueue->less ( temp_node->value, temp->value );
            while ( diff > 0 )
            {
               temp = temp->prev;
               diff = pqueue->less ( temp_node->value, temp->value );
            }
            if ( temp->next != NULL )
            {
               temp->next->prev = temp_node;
               temp_node->next = temp->next;
            }
            else
            {
               pqueue->back = temp_node;
            }
               temp_node->prev = temp;
               temp->next = temp_node;
         }
         /* Sucess */
      }
      pqueue->size++;
      pq_set_empty ( pqueue );
      return 0;
   }
}

void * pq_dequeue ( pqueue_t *pqueue )
{
   if ( pqueue->empty )
   {
      return NULL;
   }
   else
   {
      void *temp_ptr;
      temp_ptr = pqueue->front->value;
      pqnode_t *temp_node;
      temp_node = pqueue->front;
      pqueue->front = pqueue->front->next;
      if ( pqueue->front != NULL )
      {
         pqueue->front->prev = NULL;
      }
      pqueue->size--;
      pq_set_empty ( pqueue );
      free ( temp_node );
      return temp_ptr;
   }
}

void pq_destroy ( pqueue_t *pqueue )
{
   while ( !pqueue->empty )
   {
      pq_dequeue ( pqueue );
   }
   free ( pqueue );
   return;
}

void pq_set_empty ( pqueue_t *pqueue )
{
   if ( pqueue->front != NULL )
   {
      pqueue->empty = FALSE;
   }
   else
   {
      pqueue->empty = TRUE;
   }
   return;
}
